The present invention relates to the field of programmable devices, and the systems and methods for programming the same. Programmable devices, such as FPGAs, typically include thousands of programmable logic cells or blocks (PLBs) that use combinations of logic gates and/or look-up tables to perform a logic operation. Programmable devices also include a number of functional blocks having specialized logic devices adapted to specific logic operations, such as adders, multiply and accumulate circuits, phase-locked loops, and memory. The logic blocks and functional blocks are interconnected with a configurable switching circuit. The configurable switching circuit selectively routes connections between the logic blocks and functional blocks. By configuring the combination of logic blocks, functional blocks, and the switching circuit, a programmable device can be adapted to perform virtually any type of information processing function.
A typical compilation process for determining the configuration of a programmable device, referred to compilation, starts with an extraction phase, followed by a logic synthesis phase, a fitting phase, and an assembly phase. The extraction phase takes a user design, typically expressed as a netlist in a hardware description language such as Verilog or VHDL, and produces a set of logic gates implementing the user design. In the logic synthesis phase, the set of logic gates is permuted over the hardware architecture of the programmable device in order to match elements of the user design with corresponding portions of the programmable device. The fitting phase assigns the various portions of the user design to specific logic blocks and functional blocks (sometimes referred to as placement) and determines the configuration of the configurable switching circuit used to route signals between these logic blocks and functional blocks (sometimes referred to as routing), taking care to satisfy the user timing constraints as much as possible. In the assembly phase, a configuration file defining the programmable device configuration implementing the user design is created. The programmable device configuration can then be loaded into a programmable device to implement the user design. Programmable devices can be configured with the configuration during or after manufacturing.
One of the substantial challenges of the logic synthesis phase is efficiently implementing portions of the user design with programmable device resources. Often, the logic synthesis phase strives to implement portions of the user design with as few logic blocks as possible. The hardware description of user designs often includes a number of registers or flip-flops connected by numerous logic gates. Functional logic synthesis techniques evaluate the logic gates specified by the user design and determine corresponding abstract Boolean functions. These Boolean functions can then be mathematically manipulated into forms suitable for efficient implementation by the logic blocks of the programmable device.
Boolean functions can be classified as completely specified or incompletely specified. A completely specified function is fully defined for all input values. A completely specified function with N inputs typically requires of look-up table (LUT) of 2N bits to implement. An incompletely specified function is undefined for some input values. The input values corresponding with undefined function values are referred to as don't-care inputs. It is often possible to implement incompletely specified functions with N inputs with a LUT having less than 2N bits. A LUT or PLB having N inputs but less than 2N bits is referred to as an incomplete LUT or PLB. A function that can be implemented using an incomplete LUT is referred to as an incomplete function.
Many user designs include incomplete functions. For relatively simple functions, these incomplete functions can often be implemented in a single logic block. For a function having a large number of inputs, it is often necessary to implement the function using a two or more logic blocks. To implement functions using multiple logic blocks, it is necessary to determine a partitioning of function input variables among the logic block; for each logic block, an assignment of function input variables and other logic block outputs to specific logic block input ports; and to determine the data values to be stored in the one or more LUTs in each logic block.
There are several prior functional logic synthesis techniques adapted to implement incomplete functions using a minimal amount of programmable device resources. However, these prior techniques perform poorly with incomplete functions having a large number of inputs or being implemented by two or more logic blocks. For example, binary decision diagrams (BDD) solver builds a decision tree data structure that enumerate the function outputs for all combinations of input values for different potential sets of logic block input port assignments. The BDD solver then extracts patterns from this decision tree data structure to determine if a given set of potential logic block input port assignments can implement the function correctly. Typically, the BDD solver must evaluate decision tree structures for a large number of different potential logic block input port assignments before finding an acceptable logic block input port assignment. Additionally, the size of each decision tree structure increases exponentially with the number of inputs. As a result, the memory requirements for a BDD solver are too large for use with functions with a large number of inputs, such as eight or more inputs.
Another prior functional logic synthesis technique formulates the implementation of functions in one or more logic blocks as a Boolean satisfiability (SAT) problem. With this approach, Boolean satisfiability solvers, or SAT solvers, can be used to determine valid implementations of incomplete functions with one or more logic blocks. Example SAT solver algorithms are described in “FPGA technology mapping: a study of optimality,” A. Ling, D. Singh, and S. Brown, DAC, 2005, pp. 427-432, which is incorporated by reference herein. The memory requirements of SAT solvers are not as prohibitively large as those for BDD solvers. However, SAT solvers typically require long execution times to find solutions. Additionally, for very large functions, such those with ten or more input variables, the memory requirements for SAT solvers may be prohibitive.
It is therefore desirable to have a fast and efficient system and method to determine an implementation of complete or incomplete functions using single or multiple logic blocks. It is further desirable to reduce the execution time and memory requirements of SAT solvers to find valid implementations of functions. It is also desirable for the system and method to quickly screen out potential function implementations or logic block configurations that are not likely to provide acceptable results.